package bishi.kaizi;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2022/03/13 21:50
 */
public class _08 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] nums = new int[N];
        Deque<Integer> minStack = new LinkedList<>();
        Deque<Integer> maxStack = new LinkedList<>();
        int[][] maxMins = new int[N][2];
        for (int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
            while (!maxStack.isEmpty() && nums[maxStack.peekLast()] <= nums[i]) {
                maxStack.pollLast();
            }
            if (maxStack.isEmpty()) {
                maxMins[i][0] = i;//本身
                maxStack.offerLast(i);//存下标
            } else {
                maxMins[i][0] = maxStack.peekLast();//本身
                maxStack.offerLast(i);//存下标
            }
            while (!minStack.isEmpty() && nums[minStack.peekLast()] >= nums[i]) {
                minStack.pollLast();
            }
            if (minStack.isEmpty()) {
                maxMins[i][1] = i;//本身
                minStack.offerLast(i);//存下标
            } else {
                maxMins[i][1] = minStack.peekLast();//本身
                minStack.offerLast(i);//存下标
            }
        }

        while (K > 0) {
            K--;
            int left = sc.nextInt() - 1;
            int right = sc.nextInt() - 1;
            int minIndex = right;
            int maxIndex = right;
            while (maxMins[minIndex][1] != minIndex && maxMins[minIndex][1] >= left) {
                minIndex = maxMins[minIndex][1];
            }
            while (maxMins[maxIndex][0] != maxIndex && maxMins[maxIndex][0] >= left) {
                maxIndex = maxMins[maxIndex][0];
            }
            System.out.println(nums[maxIndex] - nums[minIndex]);
        }
    }
}
